package LeetCode;

public class LC_087_ScrambleString {
    public static void main(String[] args) {

    }

    static class Solution {
        public boolean isScramble(String s1, String s2) {
            char[] a1 = s1.toCharArray();
            char[] a2 = s2.toCharArray();
            return isScramble(a1, 0, a1.length - 1, a2, 0, a2.length - 1);
        }

        private boolean isScramble(char[] a1, int start1, int end1, char[] a2, int start2, int end2) {
            int[] letters = new int[26];
            boolean isSame = true;
            for (int i = start1, j = start2; i <= end1; i++, j++) {
                letters[a1[i] - 'a']++;
                letters[a2[j] - 'a']--;
                isSame = isSame && a1[i] == a2[j];
            }

            if (isSame) return true;
            for (int i = 0; i < 26; i++) if (letters[i] != 0) return false;
            for (int i = start1, j = start2; i < end1; i++, j++) {
                if (isScramble(a1, start1, i, a2, start2, j) && isScramble(a1, i + 1, end1, a2, j + 1, end2))
                    return true;
                if (isScramble(a1, start1, i, a2, end2 - j + start2, end2) && isScramble(a1, i + 1, end1, a2, start2, end2 - j + start2 - 1))
                    return true;
            }
            return false;
        }
    }
}
